import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Random;
import java.util.Vector;


public class FromZhangCode {

	static boolean finished=false;   //finish?
	static int bestone=0;  //best packing area
	static long[] area;
	static long[] carea;
	static int L,W,n,num,h;
	static Vector<pieceCoordinate> pieceorder;
	static Random rng;

	
	private static String[] splitline(String line) {
		String[] d = line.split(":");//split the line into its components
		if (d.length == 1) {//check if the file is delimited by a space, not a colon
			d = line.split(" ");
		}//end if the file uses spaces not colons
		if (d.length == 1) {//then the file is delimited by a tab, not a space or colon
			d = line.split("	");
		}//end if the file uses tabs for spacing
		return d;
	}//end method splitline

	private static void readInFromFile(REC[] pieces, String InstanceFile) {
		//READ IN DATA FROM FILE
		String problemFile = InstanceFile;
		try {
			FileReader read = new FileReader(problemFile);
			//System.out.println(problemFile);
			BufferedReader buffread = new BufferedReader(read);
			String line = "";
			int NumberOfPiecesInSet = 0;
			while (!(line.startsWith("#"))) {//this just literally counts the number of pieces in the instance
				line = buffread.readLine();
				NumberOfPiecesInSet++;
			} NumberOfPiecesInSet -= 2;//to get rid of the # and the sheet size
			buffread.close();
			read.close();
			read = new FileReader(problemFile);
			buffread = new BufferedReader(read);
			int partw = 1;//holds the width line, as a int
			int parth = 1;//holds the height line, as a int
			int i = 0;
			while (i < NumberOfPiecesInSet) {
				String[] d = splitline(buffread.readLine());//detects the delimiter and splits the line				
				try {
					int index = 0;//this means that the line will read the amount of dimensions and then the last one it reads will be the value

					partw = Integer.parseInt(d[index]);index++;
					parth = Integer.parseInt(d[index]);index++;

				} catch (NumberFormatException nf) {
					System.out.println("The numbers in the file are not in the correct format, cannot read as doubles");
					System.exit(0);
				}
				//System.out.println(i);
				pieces[i] = new REC(partw, parth);
				//System.out.println(pieces[i].length + " " + pieces[i].wide);
				//System.out.println(pieceArray[instanceSet][ins][i].width + " " + pieceArray[instanceSet][ins][i].height + " "+ pieceArray[instanceSet][ins][i].area);
				i++;
			}//end looping the lines of the file to get the piece sizes
			//now find the dimensions of the bin(s)
			String[] d = splitline(buffread.readLine());//detects the delimiter and splits the line
			W = Integer.parseInt(d[0]);//read the masterbin width
			line = buffread.readLine();
			if (!(line.startsWith("#"))) {
				System.out.println("wrong number of pieces or bins, the last line is not hash symbol");
				System.exit(0);
			}
			buffread.close();
			read.close();
		} catch (IOException a) {
			System.err.println(a.getMessage());
			System.exit(0);
		} // end catch
	}//end method readinfromfile
	

	static int canputin(REC[] lw,int[] areaoder,int k,int lx,int ly,int rx,int ry)    // verifying whether rectangule lw[areaoder[k]] can put or not
	{
		if((lw[areaoder[k]].width<=(ly-ry)&&lw[areaoder[k]].length<=(rx-lx))||(lw[areaoder[k]].width<=(rx-lx)&&lw[areaoder[k]].length<=(ly-ry)))
			return 1;
		else return 0;
	}

	static void findbest(REC[] lw,int[] areaoder,int[] loaded,int lx,int ly,int rx,int ry)
	{
		int k=n-1;
		while(k>=0&&loaded[areaoder[k]]!=0) k--;   //verifying whether all rectangule be packed or not
		if(k<0) finished=true;    // all rectangules have packed
		if(finished) return;
		k=0;
		while(k<n&&(loaded[areaoder[k]]!=0||canputin(lw,areaoder,k,lx,ly,rx,ry)==0))   //search a rectangule can be packed
			k++;
		if(k==n) return;
		if((rx-lx)>=(ly-ry))
		{//if space is strictly tall
			loaded[areaoder[k]]=1;//pack the piece, mark as packed
			num++;
			
			pieceorder.add(new pieceCoordinate(ry, lx, lw[areaoder[k]].width, lw[areaoder[k]].length, areaoder[k]));
			//if area of space on top (all the way across) is larger, then try that first, if not then try the right one first
			//we already know that the piece length is bigger than the width, from preordering
			//therefore, as the space is taller than it is wide, we try the piece upright
			//we have tested if it fits, so it must fit in this orientation
			//if it didnt, then it would not fit in the other orientation either (the slot is tall not wide)
			if((ly-ry)*(rx-lw[areaoder[k]].length)>=(ly-(ry+lw[areaoder[k]].width))*lw[areaoder[k]].length)
			{//if area on top is greater than area of right box
				if(lw[areaoder[k]].length<(rx-lx)) {//if there would be any space on the top
					findbest(lw,areaoder,loaded,lx+lw[areaoder[k]].length,ly,rx,ry);  
				}
				if(lw[areaoder[k]].width<(ly-ry)) {//if there would be any space to the right
					findbest(lw,areaoder,loaded,lx,ly,lx+lw[areaoder[k]].length,ry+lw[areaoder[k]].width);
				}
			}
			else//the area to the right is greater, do that space first
			{
				if(lw[areaoder[k]].width<(ly-ry)) {//if there would be any space to the right
					findbest(lw,areaoder,loaded,lx,ly,lx+lw[areaoder[k]].length,ry+lw[areaoder[k]].width);  
				}
				if(lw[areaoder[k]].length<(rx-lx)) {//if there would be any space on the top
					findbest(lw,areaoder,loaded,lx+lw[areaoder[k]].length,ly,rx,ry);  
				}
			}
		}
		else//if space is strictly wide
		{
			loaded[areaoder[k]]=1;
			num++;
			pieceorder.add(new pieceCoordinate(ry, lx, lw[areaoder[k]].length, lw[areaoder[k]].width, areaoder[k]));
			//if area of space to right (all the way up) is larger, then try that first, if not then try the top one first
			if((ly-(ry+lw[areaoder[k]].length))*(rx-lx)>=(rx-(lx+lw[areaoder[k]].width))*lw[areaoder[k]].length)
			{
				if(lw[areaoder[k]].length<(ly-ry))
					findbest(lw,areaoder,loaded,lx,ly,rx,ry+lw[areaoder[k]].length);   //recursionly search up area
				if(lw[areaoder[k]].width<(rx-lx))
					findbest(lw,areaoder,loaded,lx+lw[areaoder[k]].width,ry+lw[areaoder[k]].length,rx,ry);    //recursionly search right area
			}
			else
			{
				if(lw[areaoder[k]].width<(rx-lx))
					findbest(lw,areaoder,loaded,lx+lw[areaoder[k]].width,ry+lw[areaoder[k]].length,rx,ry);    //recursionly search right area
				if(lw[areaoder[k]].length<(ly-ry))
					findbest(lw,areaoder,loaded,lx,ly,rx,ry+lw[areaoder[k]].length);   //recursionly search up area
			}
		}
	}

	static void findbest2(REC[] lw,int[] areaoder,int[] loaded)
	{
		pieceorder =new Vector<pieceCoordinate>();//start of packing
		num=0;
		h=0;
		while(num<n)
			
		{   //search a rectangule can be packed
			int k=0;
			while(k<n&&(loaded[areaoder[k]]!=0))   //search a rectangule can be packed
				k++;
			if(lw[areaoder[k]].length<=W)
			{
				loaded[areaoder[k]]=1;
				num++;
				pieceorder.add(new pieceCoordinate(0, h, lw[areaoder[k]].length, lw[areaoder[k]].width, areaoder[k]));

				if(lw[areaoder[k]].length<W)
					findbest(lw,areaoder,loaded,h,W,h+lw[areaoder[k]].width,lw[areaoder[k]].length);  //recursionly packingup area
				h=h+lw[areaoder[k]].width;
			}
			else
			{
				loaded[areaoder[k]]=1;
				num++;
				pieceorder.add(new pieceCoordinate(0, h, lw[areaoder[k]].width, lw[areaoder[k]].length, areaoder[k]));

				if(lw[areaoder[k]].width<W)
					findbest(lw,areaoder,loaded,h,W,h+lw[areaoder[k]].length,lw[areaoder[k]].width);  //recursionly packingup area
				h=h+lw[areaoder[k]].length;
			}
		}
	}

	static void process(int[] t,int l,int j)   //change t[l] and t[j]
	{
		int temp;
		temp=t[l];
		t[l]=t[j];
		t[j]=temp;
	}

	static void findthebest(REC[] lw,int[] areaoder,int[] loaded, int k)
	{
		int i,j,l;
		int[] bestn = new int[n];
		
		for(l=1;l<n-1;l++)           //determine packing order: bestn
		{
			for(i=l;i<n;i++)      //determine l in bestn
			{
				for(j=0;j<n;j++)
					loaded[j]=0;
				process(areaoder,l,i);
				h=0;
				finished=false;
				findbest2(lw,areaoder,loaded);
				if(h<bestone) {
					bestone=h;
					for(j=0;j<n;j++)
						bestn[j]=areaoder[j];
				}
			}
			for(j=0;j<n;j++)
				areaoder[j]=bestn[j];
		}		
	
		for(l=1;l<n-1;l++)           //determine packing order: bestn
		{
			for(i=l;i<n;i++)      //determine l in bestn
			{
				for(j=0;j<n;j++)
					loaded[j]=0;
				process(areaoder,l,i);
				h=0;
				finished=false;
				findbest2(lw,areaoder,loaded);
				if(h<bestone) {
					bestone=h;
					for(j=0;j<n;j++)
						bestn[j]=areaoder[j];
				}
				for(j=0;j<n;j++)
					areaoder[j]=bestn[j];
			}
			for(j=0;j<n;j++)
				areaoder[j]=bestn[j];
		}
	
		for(l=1;l<n-1;l++)           //determine packing order: bestn
		{
			for(i=l;i<n;i++)      //determine l in bestn
			{
				for(j=0;j<n;j++)
					loaded[j]=0;
				process(areaoder,l,i);
				h=0;
				finished=false;
				findbest2(lw,areaoder,loaded);
				if(h<=bestone) {
					bestone=h;
					for(j=0;j<n;j++)
						bestn[j]=areaoder[j];
				}
				for(j=0;j<n;j++)
					areaoder[j]=bestn[j];
			}
			for(j=0;j<n;j++)
				areaoder[j]=bestn[j];
		}
		for(j=0;j<n;j++)    //pack bestn
			loaded[j]=0;
		finished=false;
		findbest2(lw,bestn,loaded);
//		for(j=0;j<n;j++){
//			lw[bestn[j]].print();}
		boxPrinter.printtoSVG(pieceorder, W, "test"+k, bestone);
		
	}

	static void sort(int[] t)
	{
		int i,j;
		for(i=0;i<n;i++)
			t[i]=i;
		for(i=1;i<n;i++)
		{
			//	for(j=0;j<i&&lw[t[i]].length<lw[t[j]].length;j++)  // sorting by area or perimeter from big to small
			for(j=0;j<i&&area[t[i]]<area[t[j]];j++)  // sorting by area or perimeter from big to small
				;
			for(int k=i;k>j;k--)
				t[k]=t[k-1];
			t[j]=i;
		}
	}

	public static void main(String argv[])
	{
		rng = new Random(123456);
		finished=false;
		bestone=0;
		int i;
		String fl = "";
		double sumh=0;
		double set=0;
		for(int k=0;k<21;k++)
		{
			switch (k)
			{
			case 0:
			{	L=20;n=16;fl="instances/generalise/c1p1.txt"; break;}
			case 1:
			{	L=20;n=17;fl="instances/generalise/c1p2.txt"; break;}
			case 2:
			{	L=20;n=16;fl="instances/generalise/c1p3.txt"; break;}
			case 3:
			{	L=15;n=25;fl="instances/generalise/c2p1.txt"; break;}
			case 4:
			{	L=15;n=25;fl="instances/generalise/c2p2.txt"; break;}
			case 5:
			{	L=15;n=25;fl="instances/generalise/c2p3.txt"; break;}
			case 6:
			{	L=30;n=28;fl="instances/generalise/c3p1.txt"; break;}
			case 7:
			{	L=30;n=29;fl="instances/generalise/c3p2.txt"; break;}
			case 8:
			{	L=30;n=28;fl="instances/generalise/c3p3.txt"; break;}
			case 9:
			{	L=60;n=49;fl="instances/generalise/c4p1.txt"; break;}
			case 10:
			{	L=60;n=49;fl="instances/generalise/c4p2.txt"; break;}
			case 11:
			{	L=60;n=49;fl="instances/generalise/c4p3.txt"; break;}
			case 12:
			{	L=90;n=73;fl="instances/generalise/c5p1.txt"; break;}
			case 13:
			{	L=90;n=73;fl="instances/generalise/c5p2.txt"; break;}
			case 14:
			{	L=90;n=73;fl="instances/generalise/c5p3.txt"; break;}
			case 15:
			{	L=120;;n=97;fl="instances/generalise/c6p1.txt"; break;}
			case 16:
			{	L=120;n=97;fl="instances/generalise/c6p2.txt"; break;}
			case 17:
			{	L=120;;n=97;fl="instances/generalise/c6p3.txt"; break;}
			case 18:
			{	L=240;n=196;fl="instances/generalise/c7p1.txt"; break;}
			case 19:
			{	L=240;n=197;fl="instances/generalise/c7p2.txt"; break;}
			case 20:
			{	L=240;n=196;fl="instances/generalise/c7p3.txt"; break;}
			}

			REC[] lw = new REC[n];
			readInFromFile(lw, fl);
			bestone=L+W;
			finished=true;
			//	long toarea=bestone;
			area = new long[n];
			carea = new long[n];
			int temp;
			for(i=0;i<n;i++)
			{
				if(lw[i].length<lw[i].width)
				{
					temp=lw[i].length;
					lw[i].length=lw[i].width;
					lw[i].width=temp;
				}
				area[i]=lw[i].length*lw[i].width;
				carea[i]=lw[i].length+lw[i].width;
			}
			//		for(i=0;i<n;i++)
			//		{
			//			lw[i].print();
			//		}System.out.println();
			int[] areaoder = new int[n];
			int[] loaded=new int[n];
			sort(areaoder);
			//		System.out.println(); 
			//		for(i=0;i<n;i++)
			//		{
			//			System.out.println(areaoder[i]);
			//		}

			//		for(i=0;i<n;i++)
			//		{
			//			lw[areaoder[i]].print();
			//		}
			findthebest(lw,areaoder,loaded, k);   //   (0,W-1): left up corner (L-1,0): right down corner

			//	bestone=toarea-bestone;
			//	printf("h=%d\n",bestone);
			sumh=sumh+((double)bestone/L);
			set=set+((double)bestone/L);
			System.out.println(L+ " " + W +" " + n + " " + bestone);
			if (k%3==2) {
				System.out.println(k + " " + set/3);
				set = 0;
			}
		}
		System.out.println(sumh/18);
	}
}

